package sort;

public class MyQueue {
    private static class Node {
        int val;
        Node next;
        Node prev;

        Node(int val) {
            this.val = val;
        }
    }

    public Node head; // 头指针
    public Node last; // 尾指针

    private int size; // 队列中数据个数

    public void offer(int data) {
        Node node = new Node(data);
        if (head == null) {
            head = last = node;
        }else {
            last.next = node;
            node.prev = last;
            last = node;
        }
        size++;
    }

    public int poll() {
        if (head == null) {
            throw new IndexOutOfBoundsException("下标异常");
        }

        int old = head.val;
        head = head.next;
        if (head == null) {
            // 只有一个节点
            last = null;
        }else {
            head.prev.next = null;
            head.prev = null;

        }
        size--;
        return old;
    }

    public int peek() {
        if (head == null) {
            return -1;
        }

        return head.val;
    }

    public void print() {
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    public static void main(String[] args) {
        MyQueue queue = new MyQueue();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        queue.offer(5);
        queue.print();

        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
        queue.print();
    }
}
